{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Longest Subarray LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findLongestSubarray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: # 字母与数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。</p>\n",
    "\n",
    "<p>返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>[\"A\",\"1\",\"B\",\"C\",\"D\",\"2\",\"3\",\"4\",\"E\",\"5\",\"F\",\"G\",\"6\",\"7\",\"H\",\"I\",\"J\",\"K\",\"L\",\"M\"]\n",
    "\n",
    "<strong>输出: </strong>[\"A\",\"1\",\"B\",\"C\",\"D\",\"2\",\"3\",\"4\",\"E\",\"5\",\"F\",\"G\",\"6\",\"7\"]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>[\"A\",\"A\"]\n",
    "\n",
    "<strong>输出: </strong>[]\n",
    "</pre>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>array.length <= 100000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-longest-subarray-lcci](https://leetcode.cn/problems/find-longest-subarray-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-longest-subarray-lcci](https://leetcode.cn/problems/find-longest-subarray-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        indices = {0: -1}\n",
    "        sum = 0\n",
    "        maxLength = 0\n",
    "        startIndex = -1\n",
    "        for i, s in enumerate(array):\n",
    "            if '0' <= s[0] <= '9':\n",
    "                sum += 1\n",
    "            else:\n",
    "                sum -= 1\n",
    "            if sum in indices:\n",
    "                firstIndex = indices[sum]\n",
    "                if i - firstIndex > maxLength:\n",
    "                    maxLength = i - firstIndex\n",
    "                    startIndex = firstIndex + 1\n",
    "            else:\n",
    "                indices[sum] = i\n",
    "        if maxLength == 0:\n",
    "            return []\n",
    "        return array[startIndex: startIndex + maxLength]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        last={0:-1}\n",
    "        n,ans,cur,left,right=len(array),0,0,0,-1\n",
    "        ret=[]\n",
    "        for i in range(n):\n",
    "            if 26>ord(array[i][0])-ord('A')>=0 or 26>ord(array[i][0])-ord('a')>=0 :\n",
    "                cur+=1\n",
    "            else:\n",
    "                cur-=1\n",
    "            target=cur\n",
    "            if target in last:\n",
    "                if ans<i-last[target]:\n",
    "                    ans=i-last[target]\n",
    "                    left=last[target]\n",
    "                    right=i\n",
    "            else:\n",
    "                last[target]=i\n",
    "        if right!=-1:\n",
    "            for i in range(left+1,right+1):\n",
    "                ret.append(array[i])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        q=Counter()\n",
    "        q[0]=0\n",
    "        s=0\n",
    "        i=0\n",
    "        ans=[]\n",
    "        mx=0\n",
    "        for x in array:\n",
    "            m=0\n",
    "            i+=1\n",
    "            if x.isdigit():\n",
    "               m=1\n",
    "            else:\n",
    "               m=-1\n",
    "            s+=m\n",
    "            if s in q:\n",
    "               r=i-q[s]\n",
    "               if r>mx:\n",
    "                  mx=r \n",
    "                  ans=[q[s],i]      \n",
    "            else:\n",
    "                q[s]=i\n",
    "        return array[ans[0]:ans[1]] if ans else []        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        d={}\n",
    "        d[0]=-1\n",
    "        r,l,s=0,0,0\n",
    "        len1=0\n",
    "        for i in range(len(array)):\n",
    "            if array[i].isdigit():\n",
    "                s+=1\n",
    "            else:\n",
    "                s-=1\n",
    "            if s not in d:\n",
    "                d[s]=i\n",
    "            else:\n",
    "                r=i\n",
    "                l=d[s]\n",
    "            if r-l>len1:\n",
    "                len1=r-l\n",
    "                right=r+1\n",
    "                left=l+1\n",
    "        if len1:\n",
    "            return array[left:right]\n",
    "        else:\n",
    "            return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        d={0:-1}\n",
    "        s=l=r=0\n",
    "        for i in range(len(array)):\n",
    "            s+=1 if array[i].isdigit() else -1\n",
    "            if s in d:\n",
    "                if i-d[s]>r-l:\n",
    "                    l,r=d[s],i\n",
    "            else:\n",
    "                d[s]=i\n",
    "        return array[l+1:r+1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        d = {0: -1}\n",
    "        pre = 0\n",
    "        maxl = 0\n",
    "        startindex = -1\n",
    "        for i, c in enumerate(array):\n",
    "            if c[0] in '0123456789':\n",
    "                pre += 1\n",
    "            else:\n",
    "                pre -= 1\n",
    "            if pre in d:\n",
    "                preindex = d[pre]\n",
    "                if i - preindex > maxl:\n",
    "                    maxl = i - preindex\n",
    "                    startindex = preindex + 1\n",
    "            else:\n",
    "                d[pre] = i\n",
    "        if not maxl:\n",
    "            return []\n",
    "        return array[startindex: startindex + maxl]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        index = {0:-1}\n",
    "        ans, start, end = 0, 0, 0\n",
    "        flag = 0\n",
    "        for i, ar in enumerate(array):\n",
    "            if ar.isalpha():\n",
    "                flag += 1\n",
    "            else:\n",
    "                flag -= 1\n",
    "            if flag in index:\n",
    "                if i - index[flag] > ans:\n",
    "                    ans = i - index[flag]\n",
    "                    start = index[flag] + 1\n",
    "                    end = i + 1\n",
    "            else:\n",
    "                index[flag] = i\n",
    "        return array[start:end]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        diff_pos = {}\n",
    "        letter_count, digit_count = 0, 0\n",
    "        left, right = -1, -1\n",
    "        for i in range(len(array)):\n",
    "            if array[i].isdigit():\n",
    "                digit_count += 1\n",
    "            else:\n",
    "                letter_count += 1\n",
    "            diff = letter_count - digit_count\n",
    "            if diff == 0:\n",
    "                left, right = 0, i\n",
    "            elif diff not in diff_pos:\n",
    "                diff_pos[diff] = i\n",
    "            else:\n",
    "                max_len = right - left + 1\n",
    "                temp_len = i - diff_pos[diff]\n",
    "                if temp_len > max_len or (\n",
    "                    temp_len == max_len and diff_pos[diff] < left\n",
    "                ):\n",
    "                    left, right = diff_pos[diff] + 1, i\n",
    "        return array[left : right + 1] if left != -1 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        d={}\n",
    "        d[0]=-1\n",
    "        r,l,s=0,0,0\n",
    "        len1=0\n",
    "        for i in range(len(array)):\n",
    "            if array[i].isdigit():\n",
    "                s+=1\n",
    "            else:\n",
    "                s-=1\n",
    "            if s not in d:\n",
    "                d[s]=i\n",
    "            else:\n",
    "                r=i\n",
    "                l=d[s]\n",
    "            if r-l>len1:\n",
    "                len1=r-l\n",
    "                right=r\n",
    "                left=l\n",
    "        if len1:\n",
    "            return array[left+1:right+1]\n",
    "        else:\n",
    "            return []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        d = {0: -1}\n",
    "        n = len(array)\n",
    "        n1, n2 = 0, 0\n",
    "        ans = 0\n",
    "        pos = -1\n",
    "        for i in range(n):\n",
    "            if array[i].isdigit():\n",
    "                n1 += 1\n",
    "            else:\n",
    "                n2 += 1\n",
    "            if n1 - n2 not in d:\n",
    "                d[n1 - n2] = i\n",
    "            else:\n",
    "                if i - d[n1 - n2] > ans:\n",
    "                    ans = i - d[n1 - n2]\n",
    "                    pos = d[n1 - n2] + 1\n",
    "        return array[pos: pos + ans] if ans else []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        d = {0: -1}\n",
    "        n = len(array)\n",
    "        diff = 0\n",
    "        ans = 0\n",
    "        pos = -1\n",
    "        for i in range(n):\n",
    "            if array[i].isdigit():\n",
    "                diff += 1\n",
    "            else:\n",
    "                diff -= 1\n",
    "            if diff not in d:\n",
    "                d[diff] = i\n",
    "            else:\n",
    "                if i - d[diff] > ans:\n",
    "                    ans = i - d[diff]\n",
    "                    pos = d[diff] + 1\n",
    "        return array[pos: pos + ans]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        vis = {0: -1}\n",
    "        s = mx = k = 0\n",
    "        for i, x in enumerate(array):\n",
    "            s += 1 if x.isalpha() else -1\n",
    "            if s in vis:\n",
    "                if mx < i - (j := vis[s]):\n",
    "                    mx = i - j\n",
    "                    k = j + 1\n",
    "            else:\n",
    "                vis[s] = i\n",
    "        return array[k: k + mx]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        \"\"\"\n",
    "        前缀和：统计到目前字母和数字的个数 字母+1 数字-1 \n",
    "        如果统计到j 结果为cnt 前面i的结果也是cnt 那么i-j就是满足情况的最小数组\n",
    "        且cnt加入后就不更新 因为要保证最长那肯定是越早加入越好 越长\n",
    "        \"\"\"\n",
    "        cnt = 0\n",
    "        hashtable = {0:-1} #记录前面出现的前缀和\n",
    "        maxLen,start = -1,-1 #最长的子数组长度 以及开始位置\n",
    "        for i in range(len(array)):\n",
    "            if array[i].isdigit():\n",
    "                cnt -= 1\n",
    "            else:\n",
    "                cnt += 1\n",
    "            if cnt in hashtable:\n",
    "                if i-hashtable[cnt]>maxLen or (i-hashtable[cnt]==maxLen and hashtable[cnt]<start):\n",
    "                    maxLen = i-hashtable[cnt]\n",
    "                    start = hashtable[cnt]\n",
    "            else:\n",
    "                hashtable[cnt] = i\n",
    "        return array[start+1:start+1+maxLen] if maxLen!=-1 else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        indices = {0: -1}\n",
    "        sum = 0\n",
    "        maxLength = 0\n",
    "        startIndex = -1\n",
    "        for i, s in enumerate(array):\n",
    "            if '0' <= s[0] <= '9':\n",
    "                sum += 1\n",
    "            else:\n",
    "                sum -= 1\n",
    "            if sum in indices:\n",
    "                firstIndex = indices[sum]\n",
    "                if i - firstIndex > maxLength:\n",
    "                    maxLength = i - firstIndex\n",
    "                    startIndex = firstIndex + 1\n",
    "            else:\n",
    "                indices[sum] = i\n",
    "        if maxLength == 0:\n",
    "            return []\n",
    "        return array[startIndex: startIndex + maxLength]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[\"A\",\"A\",\"1\",\"B\",\"1\",\"B\"]\n",
    "[\"A\",\"1\",\"B\",\"C\",\"D\",\"2\",\"3\",\"4\",\"E\",\"5\",\"F\",\"G\",\"6\",\"7\",\"H\",\"I\",\"J\",\"K\",\"L\",\"M\"]\n",
    "[\"A\",\"A\"]\n",
    "[\"A\",\"A\",\"1\",\"1\"]\n",
    "\n",
    "array.length <= 100000\n",
    "\n",
    "Array, Hash Table, Prefix Sum\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        cnt = 0\n",
    "        n = len(array)\n",
    "        cache = [None]*(2*n)\n",
    "        cache[n] = -1\n",
    "        maxLen = 0\n",
    "        beg = 0\n",
    "        for i in range(n):\n",
    "            cnt += 1 if array[i].isdigit() else -1\n",
    "            if cache[cnt+n] is None:\n",
    "                cache[cnt+n] = i\n",
    "            else:\n",
    "                if i - cache[cnt+n] > maxLen:\n",
    "                    beg = cache[cnt+n]+1\n",
    "                    maxLen = i - cache[cnt+n]\n",
    "        return array[beg:beg+maxLen]\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        bal = 0\n",
    "        cache = {0: -1}\n",
    "        beg = 0; maxLen = 0\n",
    "        for i in range(len(array)):\n",
    "            bal += 1 if array[i].isdigit() else -1\n",
    "            if bal not in cache:\n",
    "                cache[bal] = i\n",
    "            else:\n",
    "                if i - cache[bal] > maxLen:\n",
    "                    beg = cache[bal]+1\n",
    "                    maxLen = i - cache[bal]\n",
    "        return array[beg:beg+maxLen]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        diff = 0\n",
    "                # s,e存储最终子数组的起点和终点, 初始化e为-1, 代表没有有效解的情况\n",
    "        s, e = 0, -1\n",
    "        # 初始化diff值0的首个终点下标为-1, 用于处理子数组[0:i]的字符和数字的数目恰好相同的情况\n",
    "        diffToFirstEnd = {0: -1}\n",
    "        for i, c in enumerate(array):\n",
    "            if \"0\" <= c[0] <= \"9\":\n",
    "                # 数字, 差值加1\n",
    "                diff += 1\n",
    "            else:\n",
    "                # 字符, 差值加1\n",
    "                diff -= 1\n",
    "            if diff not in diffToFirstEnd:\n",
    "                # 前面的前缀数组中不存在当前diff, 则当前下标就是该diff对应的首个终点下标\n",
    "                diffToFirstEnd[diff] = i\n",
    "            else:\n",
    "                # 前面的前缀数组中存在当前diff, 对应的首个终点下标为firstEnd\n",
    "                # 那么[firstEnd+1:i]子数组的字符和数字个数就是相同的\n",
    "                ns = diffToFirstEnd[diff] + 1\n",
    "                if i - ns > e - s or i - ns == e - s and ns < s:\n",
    "                    # 如果当前子数组长度更长, 或对应起点更小, 则更新最终结果\n",
    "                    s, e = ns, i\n",
    "        # 区间[s,e]即为最长子数组\n",
    "        return array[s : e + 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        n = len(array)\n",
    "        nums = '0123456789'\n",
    "        acc = {0:-1}\n",
    "        total,maxlen,star = 0,0,-1\n",
    "        for i in range(n):\n",
    "            if array[i][0] in nums:\n",
    "                total-=1\n",
    "            else:\n",
    "                total+=1\n",
    "            if total in acc:\n",
    "                tmp = acc[total]\n",
    "                if i-tmp>maxlen:\n",
    "                    maxlen = i-tmp\n",
    "                    star = tmp+1\n",
    "            else:\n",
    "                acc[total] = i\n",
    "        return [] if maxlen==0 else array[star:star+maxlen]\n",
    "            \n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        indices = {0: -1}\n",
    "        sum = 0\n",
    "        maxLength = 0\n",
    "        startIndex = -1\n",
    "        for i, s in enumerate(array):\n",
    "            if '0' <= s[0] <= '9':\n",
    "                sum += 1\n",
    "            else:\n",
    "                sum -= 1\n",
    "            if sum in indices:\n",
    "                firstIndex = indices[sum]\n",
    "                if i - firstIndex > maxLength:\n",
    "                    maxLength = i - firstIndex\n",
    "                    startIndex = firstIndex + 1\n",
    "            else:\n",
    "                indices[sum] = i \n",
    "        if maxLength == 0:\n",
    "            return []\n",
    "        return array[startIndex: startIndex + maxLength]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        dmap = {0: -1} # “”的前缀和是0，对应下标-1\n",
    "        curr_sum = 0\n",
    "        maxLength = 0\n",
    "        startIndex = -1\n",
    "        for i, s in enumerate(array):\n",
    "            if '0' <= s[0] <= '9':\n",
    "                curr_sum += 1\n",
    "            else:\n",
    "                curr_sum -= 1\n",
    "            if curr_sum in dmap:\n",
    "                firstIndex = dmap[curr_sum] # 此时数字和字母个数相等\n",
    "                if i - firstIndex > maxLength:\n",
    "                    maxLength = i - firstIndex\n",
    "                    startIndex = firstIndex + 1\n",
    "            else:\n",
    "                dmap[curr_sum] = i  # 只记录第一次出现，为了最长子数组\n",
    "\n",
    "        if maxLength == 0:\n",
    "            return []\n",
    "\n",
    "        return array[startIndex: startIndex + maxLength]\n",
    "\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        n = len(array)\n",
    "        s = 0\n",
    "\n",
    "        data = {0:0}\n",
    "        start = 0\n",
    "        end = 0\n",
    "        for i in range(1, n+1):\n",
    "            if array[i-1].isdigit():\n",
    "                s += 1\n",
    "            else:\n",
    "                s += -1\n",
    "\n",
    "            if s not in data:\n",
    "                data[s] = i\n",
    "            else:\n",
    "                if end - start < i - data[s]:\n",
    "                    start = data[s]\n",
    "                    end = i\n",
    "\n",
    "        return array[start:end]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        indices={0:-1}\n",
    "        ssum=0\n",
    "        maxlength=0\n",
    "        startindex=-1\n",
    "        for i,s in enumerate(array):\n",
    "            if s[0] >= '0' and s[0] <= '9':\n",
    "                ssum += 1\n",
    "            else:\n",
    "                ssum -= 1\n",
    "            if ssum in indices:\n",
    "                firstpos = indices[ssum]\n",
    "                if i - firstpos > maxlength:\n",
    "                    maxlength = i - firstpos\n",
    "                    startindex = firstpos + 1\n",
    "            else:\n",
    "                indices[ssum] = i\n",
    "            \n",
    "        if startindex == -1:\n",
    "            return []\n",
    "        return array[startindex: startindex + maxlength]\n",
    "        \n",
    "      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        s = 0\n",
    "        pre_i = {0:0}\n",
    "        max_len = 0\n",
    "        for i, x in enumerate(array,1):\n",
    "            if x.isdigit():\n",
    "                s += 1\n",
    "            else:\n",
    "                s -= 1\n",
    "            if s in pre_i:\n",
    "                l = pre_i[s]\n",
    "                if i-l > max_len:\n",
    "                    max_len = i-l\n",
    "                    ans = [l,i]\n",
    "            if s not in pre_i:\n",
    "                pre_i[s] = i\n",
    "        if max_len > 0:\n",
    "            return array[ans[0]:ans[1]]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        indices = {0: -1}\n",
    "        sum = 0\n",
    "        maxLength = 0\n",
    "        startIndex = -1\n",
    "        for i, s in enumerate(array):\n",
    "            if '0' <= s[0] <= '9':\n",
    "                sum += 1\n",
    "            else:\n",
    "                sum -= 1\n",
    "            if sum in indices:\n",
    "                firstIndex = indices[sum]\n",
    "                if i - firstIndex > maxLength:\n",
    "                    maxLength = i - firstIndex\n",
    "                    startIndex = firstIndex + 1\n",
    "            else:\n",
    "                indices[sum] = i\n",
    "        if maxLength == 0:\n",
    "            return []\n",
    "        return array[startIndex: startIndex + maxLength]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        d = dict()\n",
    "        l = 0\n",
    "        r = -1\n",
    "        s = 0\n",
    "\n",
    "        for i in range(len(array)):\n",
    "            if '0' <= array[i] <= '9999999999999999999999999999':\n",
    "                s += 1\n",
    "            else:\n",
    "                s -= 1\n",
    "            \n",
    "            if s == 0:\n",
    "                l,r = 0, i\n",
    "            else:\n",
    "                if s in d:\n",
    "                    if i-(d[s]+1) > r-l:\n",
    "                        l, r = d[s]+1, i\n",
    "                else:\n",
    "                    d[s] = i\n",
    "        return array[l:r+1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        d = {0: -1}\n",
    "        n = len(array)\n",
    "        n1, n2 = 0, 0\n",
    "        ans = 0\n",
    "        pos = -1\n",
    "        for i in range(n):\n",
    "            if array[i].isdigit():\n",
    "                n1 += 1\n",
    "            else:\n",
    "                n2 += 1\n",
    "            if n1 - n2 not in d:\n",
    "                d[n1 - n2] = i\n",
    "            else:\n",
    "                if i - d[n1 - n2] > ans:\n",
    "                    ans = i - d[n1 - n2]\n",
    "                    pos = d[n1 - n2] + 1\n",
    "        return array[pos: pos + ans]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        idxs = {0: -1}\n",
    "        n = len(array)\n",
    "        left, right, curMax, prefix = 0, 0, 0, 0\n",
    "        for i in range(n):\n",
    "            if array[i][0] >= '0' and array[i][0] <= '9':\n",
    "                prefix += 1\n",
    "            else:\n",
    "                prefix -= 1\n",
    "            if prefix not in idxs:\n",
    "                idxs[prefix] = i\n",
    "            if prefix in idxs:\n",
    "                idx = idxs[prefix]\n",
    "                if i - idx > curMax:\n",
    "                    curMax = i - idx\n",
    "                    left = idx + 1\n",
    "                    right = i + 1\n",
    "\n",
    "        return array[left : right]\n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        maxlength=0\n",
    "        index={0:-1}\n",
    "        sum_=0\n",
    "        startindex=-1\n",
    "\n",
    "        for i,ch in enumerate(array):\n",
    "            if '0'<=ch[0]<='9':\n",
    "                sum_+=1\n",
    "            else:\n",
    "                sum_-=1\n",
    "            \n",
    "            if sum_ in index:\n",
    "                firstindex=index[sum_]\n",
    "                if i-firstindex>maxlength:\n",
    "                    \n",
    "                    maxlength=i-firstindex\n",
    "                    startindex=firstindex+1\n",
    "            else:\n",
    "                index[sum_]=i\n",
    "        if maxlength==0:\n",
    "            return []\n",
    "        else:\n",
    "            return array[startindex:startindex+maxlength]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        maxlen = 0\n",
    "        s,e = -1,-1\n",
    "        n = len(array)\n",
    "\n",
    "        def isNumber(a):\n",
    "            return a[0] >= '0' and a[0] <= '9'\n",
    "\n",
    "        diff = {0:-1}\n",
    "        curdiff = 0\n",
    "        for i in range(n):\n",
    "            if isNumber(array[i]):\n",
    "                curdiff += 1\n",
    "            else:\n",
    "                curdiff -= 1\n",
    "\n",
    "            if curdiff in diff:\n",
    "                curlen = i - diff[curdiff]\n",
    "                if curlen > maxlen:\n",
    "                    maxlen = curlen\n",
    "                    s,e = diff[curdiff]+1, i\n",
    "            else:\n",
    "                diff[curdiff] = i\n",
    "        \n",
    "        if maxlen > 0:\n",
    "            return array[s:e+1]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        d = dict()\n",
    "        l = 0\n",
    "        r = -1\n",
    "        s = 0\n",
    "\n",
    "        for i in range(len(array)):\n",
    "            if '0' <= array[i][0] <= '9':\n",
    "                s += 1\n",
    "            else:\n",
    "                s -= 1\n",
    "            \n",
    "            if s == 0:\n",
    "                l,r = 0, i\n",
    "            else:\n",
    "                if s in d:\n",
    "                    if i-(d[s]+1) > r-l:\n",
    "                        l, r = d[s]+1, i\n",
    "                else:\n",
    "                    d[s] = i\n",
    "        return array[l:r+1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        n = len(array)\n",
    "        nums = '0123456789'\n",
    "        acc = {0:-1}\n",
    "        total,maxlen,star = 0,0,-1\n",
    "        for i in range(n):\n",
    "            if array[i][0] in nums:\n",
    "                total-=1\n",
    "            else:\n",
    "                total+=1\n",
    "            if total in acc:\n",
    "                tmp = acc[total]\n",
    "                if i-tmp>maxlen:\n",
    "                    maxlen = i-tmp\n",
    "                    star = tmp+1\n",
    "            else:\n",
    "                acc[total] = i\n",
    "        return [] if maxlen==0 else array[star:star+maxlen]\n",
    "            \n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        n = len(array)\n",
    "        mx = sm = 0\n",
    "        idx = n\n",
    "        cnt = dict()\n",
    "        cnt[0] = -1\n",
    "        for i, x in enumerate(array):\n",
    "            sm += 1 if x.isdigit() else -1\n",
    "            if sm in cnt:\n",
    "                if mx < i - cnt[sm] + 1:\n",
    "                    mx = i - cnt[sm] + 1\n",
    "                    idx = cnt[sm]\n",
    "            else:\n",
    "                cnt[sm] = i\n",
    "        if idx == n:\n",
    "            return []\n",
    "        return [array[i] for i in range(idx+1, idx+mx)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        d = dict()\n",
    "        l = 0\n",
    "        r = -1\n",
    "        s = 0\n",
    "\n",
    "        for i in range(len(array)):\n",
    "            if '0' <= array[i] <= '99999999':\n",
    "                s += 1\n",
    "            else:\n",
    "                s -= 1\n",
    "            \n",
    "            if s == 0:\n",
    "                l,r = 0, i\n",
    "            else:\n",
    "                if s in d:\n",
    "                    if i-(d[s]+1) > r-l:\n",
    "                        l, r = d[s]+1, i\n",
    "                else:\n",
    "                    d[s] = i\n",
    "        return array[l:r+1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        d = dict()\n",
    "        l = 0\n",
    "        r = -1\n",
    "        s = 0\n",
    "\n",
    "        for i in range(len(array)):\n",
    "            if '0' <= array[i][0] <= '9':\n",
    "                s += 1\n",
    "            else:\n",
    "                s -= 1\n",
    "            \n",
    "            if s == 0:\n",
    "                l,r = 0, i\n",
    "            else:\n",
    "                if s in d:\n",
    "                    if i-(d[s]+1) > r-l:\n",
    "                        l, r = d[s]+1, i\n",
    "                else:\n",
    "                    d[s] = i\n",
    "        return array[l:r+1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        maxlength=0\n",
    "        index={0:-1}\n",
    "        sum_=0\n",
    "        startindex=-1\n",
    "\n",
    "        for i,ch in enumerate(array):\n",
    "            if '0'<=ch[0]<='9':\n",
    "                sum_+=1\n",
    "            else:\n",
    "                sum_-=1\n",
    "            \n",
    "            if sum_ in index:\n",
    "                firstindex=index[sum_]\n",
    "                if i-firstindex>maxlength:\n",
    "                    \n",
    "                    maxlength=i-firstindex\n",
    "                    startindex=firstindex+1\n",
    "            else:\n",
    "                index[sum_]=i\n",
    "        if maxlength==0:\n",
    "            return []\n",
    "        else:\n",
    "            return array[startindex:startindex+maxlength]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        vis = {0: -1}\n",
    "        s = mx = k = 0\n",
    "        for i, x in enumerate(array):\n",
    "            s += 1 if x.isalpha() else -1\n",
    "            if s in vis:\n",
    "                if mx < i - (j := vis[s]):\n",
    "                    mx = i - j\n",
    "                    k = j + 1\n",
    "            else:\n",
    "                vis[s] = i\n",
    "        return array[k: k + mx]\n",
    "\n",
    "\n",
    "# 方法一：前缀和 + 哈希表\n",
    "# 题目要求找到最长的子数组，且包含的字符和数字的个数相同。我们可以将字符看作 111，数字看作 −1-1−1，那么问题就转化为：求最长的子数组，使得该子数组的和为 000。\n",
    "# 我们可以运用前缀和的思想，用哈希表 visvisvis 记录每个前缀和第一次出现的位置，用变量 mxmxmx 和 kkk 分别记录最长的满足条件的子数组的长度和左端点位置。\n",
    "# 作者：ylb\n",
    "# 链接：https://leetcode.cn/problems/find-longest-subarray-lcci/solutions/2160652/python3javacgotypescript-yi-ti-yi-jie-qi-qy7i/\n",
    "# 来源：力扣（LeetCode）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        indices = {0: -1}\n",
    "        sum = 0\n",
    "        max_length = 0\n",
    "        start_index = -1\n",
    "\n",
    "        for i, s in enumerate(array):\n",
    "            if '0' <= s[0] <= '9':\n",
    "                # 将数字都视为1\n",
    "                sum += 1\n",
    "            else:\n",
    "                # 将字母都视为-1\n",
    "                sum -= 1\n",
    "\n",
    "            if sum in indices:\n",
    "                first_index = indices[sum]\n",
    "                if i - first_index > max_length:\n",
    "                    max_length = i - first_index\n",
    "                    start_index = first_index + 1\n",
    "            else:\n",
    "                indices[sum] = i\n",
    "\n",
    "        if max_length == 0:\n",
    "            return []\n",
    "        else:\n",
    "            return array[start_index: start_index + max_length]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        record = {}\n",
    "        count = 0\n",
    "        record[0] = -1\n",
    "        max_len = 0\n",
    "        left = 0\n",
    "        for i, c in enumerate(array):\n",
    "            if c.isdigit():\n",
    "                count += 1\n",
    "            else:\n",
    "                count -= 1\n",
    "            if count not in record:\n",
    "                record[count] = i\n",
    "            else:\n",
    "                if i-record[count] > max_len:\n",
    "                    max_len = i-record[count]\n",
    "                    left = record[count]\n",
    "                print(max_len, left)\n",
    "        # print(record)\n",
    "        return array[left+1:left+max_len+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        array2 = list(array)\n",
    "        for i in range(len(array)):\n",
    "            if len(array[i]) == 1:\n",
    "                if ord('A')<=ord(array[i])<=ord('Z'):\n",
    "                    array2[i] = 1 \n",
    "                elif ord('a')<=ord(array[i])<=ord('z'):\n",
    "                    array2[i] = 1\n",
    "                else:\n",
    "                    array2[i] = -1 \n",
    "            else:\n",
    "                array2[i] = -1 \n",
    "            \n",
    "        presum_dict = {0: -1}\n",
    "        presum = 0\n",
    "        max_len = 0\n",
    "        left = 0\n",
    "        for i in range(len(array)):\n",
    "            presum += array2[i]\n",
    "            if presum in presum_dict.keys():\n",
    "                if max_len < i-presum_dict[presum]:\n",
    "                    max_len = i - presum_dict[presum]\n",
    "                    left = presum_dict[presum] + 1\n",
    "            else:\n",
    "                presum_dict[presum] = i \n",
    "        \n",
    "        return array[left: left+max_len]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "\n",
    "        n = len(array)\n",
    "        tmp = [0] * n\n",
    "        for i in range(n):\n",
    "            tmp[i] = 1 if array[i].isdigit() else -1\n",
    "        \n",
    "        dic = {}\n",
    "        dic[0] = -1\n",
    "        sum = 0\n",
    "        length = 0\n",
    "        start, end = 0, -1\n",
    "        for j in range(n):\n",
    "            sum += tmp[j]\n",
    "\n",
    "            if sum in dic:\n",
    "                if j - dic[sum] > length:\n",
    "                    length = j - dic[sum]\n",
    "                    start = dic[sum] + 1\n",
    "                    end = j\n",
    "            else:\n",
    "                dic[sum] = j\n",
    "        return array[start:end+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlpha(self, string: str) -> bool:\n",
    "        for c in string:\n",
    "            if ord('A')<=ord(c)<=ord('Z'):\n",
    "                return True\n",
    "            elif ord('a')<=ord(c)<=ord('z'):\n",
    "                return True \n",
    "        return False \n",
    "\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        array2 = list(array)\n",
    "        for i in range(len(array)):\n",
    "            if self.isAlpha(array[i]):\n",
    "                array2[i] = 1 \n",
    "            else:\n",
    "                array2[i] = -1 \n",
    "            \n",
    "        presum_dict = {0: -1}\n",
    "        presum = 0\n",
    "        max_len = 0\n",
    "        left = 0\n",
    "        for i in range(len(array)):\n",
    "            presum += array2[i]\n",
    "            if presum in presum_dict:\n",
    "                if max_len < i-presum_dict[presum]:\n",
    "                    max_len = i - presum_dict[presum]\n",
    "                    left = presum_dict[presum] + 1\n",
    "            else:\n",
    "                presum_dict[presum] = i \n",
    "        \n",
    "        return array[left: left+max_len]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlpha(self, string: str) -> bool:\n",
    "        for c in string:\n",
    "            if ord('A')<=ord(c)<=ord('Z'):\n",
    "                return True\n",
    "            elif ord('a')<=ord(c)<=ord('z'):\n",
    "                return True \n",
    "        return False \n",
    "\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        array2 = list(array)\n",
    "        for i in range(len(array)):\n",
    "            if self.isAlpha(array[i]):\n",
    "                array2[i] = 1 \n",
    "            else:\n",
    "                array2[i] = -1 \n",
    "            \n",
    "        presum_dict = {0: -1}\n",
    "        presum = 0\n",
    "        max_len = 0\n",
    "        left = 0\n",
    "        for i in range(len(array)):\n",
    "            presum += array2[i]\n",
    "            if presum in presum_dict.keys():\n",
    "                if max_len < i-presum_dict[presum]:\n",
    "                    max_len = i - presum_dict[presum]\n",
    "                    left = presum_dict[presum] + 1\n",
    "            else:\n",
    "                presum_dict[presum] = i \n",
    "        \n",
    "        return array[left: left+max_len]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "\n",
    "        ls = []\n",
    "\n",
    "        for a in array:\n",
    "            if a.isdigit():\n",
    "                ls.append(1)\n",
    "            else:\n",
    "                ls.append(-1)\n",
    "\n",
    "\n",
    "        mp = {}\n",
    "        mp[0] = -1\n",
    "\n",
    "        res = -1\n",
    "        left = None\n",
    "\n",
    "        sum_ = 0\n",
    "        for i, n in enumerate(ls):\n",
    "            sum_ += n\n",
    "            if sum_ in mp:\n",
    "                size = i - mp[sum_]\n",
    "\n",
    "                if size > res:\n",
    "                    res = size\n",
    "                    left = mp[sum_] + 1\n",
    "            else:\n",
    "                mp[sum_] = i\n",
    "\n",
    "        if res == -1:\n",
    "            return []\n",
    "        else:\n",
    "            return array[left:left + res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        find = {0 : -1}\n",
    "        max_len = 0\n",
    "        max_left = 0\n",
    "        max_right = 0\n",
    "        sum_num = 0\n",
    "        n = len(array)\n",
    "        for i in range(n):\n",
    "            if array[i].isdigit():\n",
    "                ans.append(1)\n",
    "            else:\n",
    "                ans.append(-1)\n",
    "            \n",
    "            sum_num += ans[i]\n",
    "            if sum_num in find:\n",
    "                if i - find[sum_num] > max_len:\n",
    "                    max_left = find[sum_num]\n",
    "                    max_right = i\n",
    "                    max_len = i - find[sum_num]\n",
    "            # elif sum_num == 0:\n",
    "            #     if i + 1 > max_len:\n",
    "            #         max_left = 0\n",
    "            #         max_right = i + 1\n",
    "            #         max_len = i + 1\n",
    "            \n",
    "\n",
    "            else:\n",
    "                find[sum_num] = i\n",
    "        \n",
    "        return array[max_left + 1: max_right + 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        n = len(array)\n",
    "        cur = 0\n",
    "        res = 0\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        pres = {}\n",
    "\n",
    "        for i in range(n):\n",
    "            if not array[i].isdigit():\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur -= 1\n",
    "\n",
    "            if cur == 0:\n",
    "                res = i+1\n",
    "                ans = array[0:i+1]\n",
    "\n",
    "            else:\n",
    "                if cur in pres:\n",
    "                    if i-pres[cur] > res:\n",
    "                        res = i-pres[cur]\n",
    "                        ans = array[pres[cur]+1:i+1]\n",
    "\n",
    "            if cur not in pres:\n",
    "                pres[cur] = i\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        indexlist={0:-1}\n",
    "        letter=0\n",
    "        number=0\n",
    "        res=[]\n",
    "        for idx,i in enumerate(array):\n",
    "            if 'A'<=i<='Z' or 'a'<=i<='z' :\n",
    "                letter+=1\n",
    "            else:\n",
    "                number+=1\n",
    "            if letter-number in indexlist:\n",
    "                if idx-indexlist[letter-number]>len(res):\n",
    "                    res=array[indexlist[letter-number]+1:idx+1]\n",
    "\n",
    "            else:\n",
    "                indexlist[letter-number]= idx\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        begin = end = 0\n",
    "        s = n = len(array)\n",
    "        first = [-1] * (n * 2 + 1)\n",
    "        first[s] = 0\n",
    "        # start from array[1]\n",
    "        for i, v in enumerate(array, 1):\n",
    "            s += -1 if v[0].isdigit() else 1\n",
    "            j = first[s]\n",
    "            if j < 0:\n",
    "                first[s] = i\n",
    "            elif i - j > end - begin:\n",
    "                begin, end = j, i\n",
    "        return array[begin:end]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        n = len(array)\n",
    "        cnt = 0\n",
    "        memo = [-2]*(2*n+1)\n",
    "        memo[n] = -1\n",
    "        left, right = 0, 0\n",
    "        maxl = 0\n",
    "        for i in range(n):\n",
    "            if array[i].isdigit():\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt -= 1\n",
    "            if memo[cnt+n] != -2 and i-memo[cnt+n] > maxl:\n",
    "                maxl = i-memo[cnt+n]\n",
    "                left = memo[cnt+n]+1\n",
    "                right = i+1\n",
    "            elif memo[cnt+n] == -2:\n",
    "                memo[cnt+n] = i\n",
    "        return array[left:right]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[\"A\",\"A\",\"1\",\"B\",\"1\",\"B\"]\n",
    "[\"A\",\"1\",\"B\",\"C\",\"D\",\"2\",\"3\",\"4\",\"E\",\"5\",\"F\",\"G\",\"6\",\"7\",\"H\",\"I\",\"J\",\"K\",\"L\",\"M\"]\n",
    "[\"A\",\"A\"]\n",
    "[\"A\",\"A\",\"1\",\"1\"]\n",
    "\n",
    "array.length <= 100000\n",
    "\n",
    "Array, Hash Table, Prefix Sum\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        cnt = 0\n",
    "        n = len(array)\n",
    "        cache = [None]*(2*n)\n",
    "        cache[n] = -1\n",
    "        maxLen = 0\n",
    "        beg = 0\n",
    "        for i in range(n):\n",
    "            cnt += 1 if array[i].isdigit() else -1\n",
    "            if cache[cnt+n] is None:\n",
    "                cache[cnt+n] = i\n",
    "            else:\n",
    "                if i - cache[cnt+n] > maxLen:\n",
    "                    beg = cache[cnt+n]+1\n",
    "                    maxLen = i - cache[cnt+n]\n",
    "        return array[beg:beg+maxLen]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        # s = list(accumulate((-1 if v[0].isdigit() else 1 for v in array), initial = 0)) # 前缀和数组\n",
    "        # begin = end = 0 # 符合要求的子数组[begin, end]\n",
    "        # first = {}\n",
    "        # for i, v in enumerate(s):\n",
    "        #     j = first.get(v, -1)\n",
    "        #     if j < 0: # 首次遇到s[i]\n",
    "        #         first[v] = i\n",
    "        #     elif i - j > end - begin: # 更长的子数组\n",
    "        #         begin, end = j, i\n",
    "        # return array[begin: end]\n",
    "\n",
    "    # 优化： 前缀和数组可以简化一个整数变量， 一边遍历array 一边计算s\n",
    "        begin = end = 0\n",
    "        s = n = len(array)\n",
    "        first = [-1] * (n * 2 + 1)\n",
    "        first[s] = 0  # s[0] = 0\n",
    "        for i, v in enumerate(array, 1):\n",
    "            s += -1 if v[0].isdigit() else 1\n",
    "            j = first[s]\n",
    "            if j < 0:\n",
    "                first[s] = i\n",
    "            elif i - j > end - begin:\n",
    "                begin, end = j, i\n",
    "        return array[begin:end]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        begin = end = 0\n",
    "        s = list(accumulate((-1 if v.isdigit() else 1 for v in array), initial=0))\n",
    "        first = {}\n",
    "        for i, v in enumerate(s):\n",
    "            j = first.get(v, -1)\n",
    "            if j < 0:\n",
    "                first[v] = i\n",
    "            elif i - j > end - begin:\n",
    "                begin, end = j, i\n",
    "        return array[begin:end]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        s = list(accumulate((-1 if v[0].isdigit() else 1 for v in array), initial = 0)) # 前缀和数组\n",
    "        begin = end = 0 # 符合要求的子数组[begin, end]\n",
    "        first = {}\n",
    "        for i, v in enumerate(s):\n",
    "            j = first.get(v, -1)\n",
    "            if j < 0: # 首次遇到s[i]\n",
    "                first[v] = i\n",
    "            elif i - j > end - begin: # 更长的子数组\n",
    "                begin, end = j, i\n",
    "        return array[begin: end]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        begin = end = 0\n",
    "        s = list(accumulate((-1 if v.isdigit() else 1 for v in array), initial=0))\n",
    "        first = {}\n",
    "        for i, v in enumerate(s):\n",
    "            j = first.get(v, -1)\n",
    "            if j < 0:\n",
    "                first[v] = i\n",
    "            elif i - j > end - begin:\n",
    "                begin, end = j, i\n",
    "        return array[begin:end]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        s=list(accumulate((-1 if v[0].isdigit() else 1 for v in array),initial=0))\n",
    "        begin=end=0\n",
    "        first={}\n",
    "        for i,v in enumerate(s):\n",
    "            j=first.get(v,-1)\n",
    "            if j <0:\n",
    "                first[v]=i\n",
    "            elif i-j>end-begin:\n",
    "                begin,end=j,i\n",
    "        return array[begin:end]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "\n",
    "        s = list( accumulate((-1 if v[0].isdigit() else 1 for v in array), initial=0) )\n",
    "\n",
    "        begin = end = 0\n",
    "        first = {}\n",
    "\n",
    "        for i, v in enumerate(s):\n",
    "            j = first.get(v, -1)\n",
    "\n",
    "            if j<0:\n",
    "                first[v] = i\n",
    "            elif i-j > end-begin:\n",
    "                begin, end = j, i\n",
    "        \n",
    "\n",
    "        return array[begin:end]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        n = len(array)\n",
    "        begin = end = 0\n",
    "        first = {}\n",
    "        s = list(accumulate((-1 if v[0].isdigit() else 1 for v in array), initial = 0))\n",
    "\n",
    "        for i,v in enumerate(s):\n",
    "            j = first.get(v,-1)\n",
    "            if j < 0:\n",
    "                first[v] = i \n",
    "            elif i - j > end - begin:\n",
    "                begin,end = j,i \n",
    "        return array[begin:end]\n",
    "       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# import collections\n",
    "# class Solution:\n",
    "#     def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "#         #1-字母和数字分别用1和-1表示，\n",
    "#         #2-字母和数字的个数相同可以转化为子数组和为0，\n",
    "#         #3-子数组和为0转换为left和right的前缀和相同，找到最长的right-left\n",
    "#         #4-用字典或哈希表存储 前缀和为i的元素index\n",
    "#         dict1 = collections.defaultdict(list)\n",
    "#         list1 = []\n",
    "#         n = len(array)\n",
    "#         pre = [0]*(n+1)\n",
    "#         pre[0] = 0\n",
    "        \n",
    "#         for i in range(n):\n",
    "#             if(array[i]>='0' and array[i]<='9'):\n",
    "#                 list1.append(-1)\n",
    "#             else:\n",
    "#                 list1.append(1)\n",
    "#             pre[i+1] = pre[i]+list1[i]\n",
    "#             dict1[pre[i+1]].append(i+1)\n",
    "#         dict1[0].insert(0,0)\n",
    "#         res = 0\n",
    "#         ans = []\n",
    "#         print(pre)\n",
    "#         print(dict1)\n",
    "#         for key in dict1.keys():\n",
    "#             start = dict1[key][0]\n",
    "#             end = dict1[key][-1]\n",
    "#             if(res<end-start-1):\n",
    "#                 res = end-start-1\n",
    "#                 if(start>0):\n",
    "#                     ans = array[start-1:end-1]\n",
    "#                 else:\n",
    "#                     ans = array[start:end]\n",
    "#         return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        s = list(accumulate((-1 if v[0].isdigit() else 1 for v in array), initial=0)) #s为前缀和数组\n",
    "        begin = end = 0  # 符合要求的子数组 [begin,end)\n",
    "        dict1 = {}\n",
    "        for i, v in enumerate(s):\n",
    "            j = dict1.get(v, -1)\n",
    "            if j < 0:  # 首次遇到 s[i]\n",
    "                dict1[v] = i\n",
    "            elif i - j > end - begin:  # 更长的子数组\n",
    "                begin, end = j, i\n",
    "            #只保存前缀和相同元素第一次出现和最后一次出现\n",
    "        return array[begin:end]\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        numCnt, letterCnt = 0, 0\n",
    "        pre = [0]\n",
    "        gap = {}\n",
    "        gap[0] = -1\n",
    "        for i, v in enumerate(array):\n",
    "            if v.isdigit():\n",
    "                numCnt += 1\n",
    "            else:\n",
    "                letterCnt += 1\n",
    "            pre.append(numCnt-letterCnt)\n",
    "            gap[numCnt-letterCnt] = i\n",
    "        left, right = 0, gap[0]\n",
    "        size = right - left\n",
    "        for i, v in enumerate(pre):\n",
    "            j = gap[v]\n",
    "            if j - i > size:\n",
    "                left, right = i, j\n",
    "                size = j - i\n",
    "        return array[left:right+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        shuzi = [9] * len(array)\n",
    "        for i, v in enumerate(array):\n",
    "            if v.isdigit():\n",
    "                shuzi[i] = -1\n",
    "            else:\n",
    "                shuzi[i] = 1\n",
    "\n",
    "        s = list(accumulate(shuzi, initial=0))\n",
    "        s_hash = {}\n",
    "        start, end = 0, 0\n",
    "        for i, v in enumerate(s):\n",
    "            j = s_hash.get(v, -1)\n",
    "            if j < 0:\n",
    "                s_hash[v] = i\n",
    "            elif i - j > end - start:\n",
    "                end = i\n",
    "                start = j\n",
    "\n",
    "        return array[start:end]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        if len(array) <= 1:return []\n",
    "        n = len(array)\n",
    "        tmp = [0]*n\n",
    "    \n",
    "        for i in range(n):\n",
    "            if array[i].isdigit():\n",
    "                tmp[i] = 1\n",
    "            else:\n",
    "                tmp[i] = -1\n",
    "        tmp = list(accumulate(tmp,initial=0))\n",
    "        res = 0\n",
    "        mp = defaultdict(int)\n",
    "        out = []\n",
    "        for i in range(n+1):\n",
    "            if tmp[i] in mp and i-mp[tmp[i]]>res:\n",
    "                res = i-mp[tmp[i]]\n",
    "                out = array[mp[tmp[i]]:i]\n",
    "            elif tmp[i] not in mp:\n",
    "                mp[tmp[i]] = i\n",
    "        print(res)\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        from itertools import accumulate\n",
    "        # 把数字置为-1，字母置为1，获取前缀和\n",
    "        fsum=list(accumulate([-1 if v.isdigit() else 1 for v in array],initial=0))\n",
    "        begin,end = 0, 0\n",
    "        x = dict()\n",
    "        for i, k in enumerate(fsum):\n",
    "            # 前缀和第一次出现的位置\n",
    "            if k not in x:\n",
    "                x[k] = i\n",
    "            elif i - x[k] > end - begin:\n",
    "                    begin, end = x[k], i\n",
    "        return array[begin:end]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        start = end = 0\n",
    "        s = [0 for _ in range(len(array) + 1)]\n",
    "        for i in range(1, len(array) + 1):\n",
    "            if array[i-1].isdigit() :\n",
    "                s[i] = s[i-1] + 1\n",
    "            else :\n",
    "                s[i] = s[i-1] - 1\n",
    "        #s = list(accumulate(-1 if v.isdigit() else 1 for v in array))\n",
    "        print(\"s : {}\".format(s))\n",
    "        s_map = {}\n",
    "        for i, v in enumerate(s):\n",
    "            if s_map.get(v) is not None:\n",
    "                if (i - s_map.get(v)) > end - start:\n",
    "                    start = s_map.get(v)\n",
    "                    end = i\n",
    "            else :\n",
    "                s_map[v] = i\n",
    "        print(s_map)\n",
    "        return array[start : end]\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        s=list(accumulate([-1 if v.isdigit() else 1 for v in array],initial=0))\n",
    "        begin,end=0,0\n",
    "        x=dict()\n",
    "        for i,k in enumerate(s):\n",
    "            if k not in x:\n",
    "                x[k]=i\n",
    "            else:\n",
    "                if i-x[k]>end-begin:\n",
    "                    begin=x[k]\n",
    "                    end=i\n",
    "        return array[begin:end]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        from itertools import accumulate\n",
    "\n",
    "        fsum = list(accumulate([-1 if v.isdigit() else 1 for v in array],initial = 0))\n",
    "        l,r = 0,0\n",
    "        x = {}\n",
    "        for i,k in enumerate(fsum):\n",
    "            if k not in x:\n",
    "                x[k] = i\n",
    "            else:\n",
    "                if i - x[k] > r-l:\n",
    "                    l,r = x[k],i \n",
    "        return array[l:r]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        n = len(array)\n",
    "        def is_num(c):\n",
    "            return c >= \"0\" and c <= \"9\"\n",
    "        subti = [1 if is_num(a[0]) else -1 for a in array]\n",
    "        pre = [0 for _ in range(n)]\n",
    "        pre[0] = subti[0]\n",
    "        helper = {0: -1, subti[0]: 0}\n",
    "        #print(subti)\n",
    "        \n",
    "        max_l, pos = 0, -1\n",
    "        for i in range(1, n):\n",
    "            pre[i] = pre[i-1] + subti[i]\n",
    "            if pre[i] not in helper:\n",
    "                helper[pre[i]] = i\n",
    "            else:\n",
    "                if i - helper[pre[i]] > max_l:\n",
    "                    max_l = i - helper[pre[i]]\n",
    "                    pos = i\n",
    "        return array[pos - max_l + 1: pos+1]\n",
    "            \n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        from itertools import accumulate\n",
    "        fsum=list(accumulate([-1 if v.isdigit() else 1 for v in array],initial=0))\n",
    "        begin,end=0,0\n",
    "        x=dict()\n",
    "        for i,k in enumerate(fsum):\n",
    "            if k not in x:\n",
    "                x[k]=i\n",
    "            else:\n",
    "                if i-x[k]>end-begin:\n",
    "                    begin,end=x[k],i\n",
    "        return array[begin:end]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        from itertools import accumulate\n",
    "        fsum=list(accumulate([-1 if v.isdigit() else 1 for v in array],initial=0))\n",
    "        begin,end=0,0\n",
    "        x=dict()\n",
    "        for i,k in enumerate(fsum):\n",
    "            if k not in x:\n",
    "                x[k]=i\n",
    "            else:\n",
    "                if i-x[k]>end-begin:\n",
    "                    begin,end=x[k],i\n",
    "        return array[begin:end]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        from itertools import accumulate\n",
    "        fsum=list(accumulate([-1 if v.isdigit() else 1 for v in array], initial=0))\n",
    "        begin,end = 0, 0\n",
    "        x = dict()\n",
    "        for i, k in enumerate(fsum):\n",
    "            if k not in x:\n",
    "                x[k] = i\n",
    "            elif i - x[k] > end - begin:\n",
    "                begin, end = x[k], i\n",
    "        return array[begin:end]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        from itertools import accumulate\n",
    "        fsum=list(accumulate([-1 if v.isdigit() else 1 for v in array],initial=0))\n",
    "        begin,end = 0, 0\n",
    "        x = dict()\n",
    "        for i, k in enumerate(fsum):\n",
    "            if k not in x:\n",
    "                x[k] = i\n",
    "            elif i - x[k] > end - begin:\n",
    "                begin, end = x[k], i\n",
    "        return array[begin:end]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        s = list(accumulate([-1 if x.isdigit() else 1 for x in array],initial = 0))\n",
    "        # print(s)\n",
    "        first = {}\n",
    "        start = end = 0\n",
    "        for i, x in enumerate(s):\n",
    "            j = first.get(x,-2)\n",
    "            if j < 0:\n",
    "                first[x] = i\n",
    "            elif end - start < i-j:\n",
    "                start,end = j,i\n",
    "            # print(first)\n",
    "        return array[start:end]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        if len(array) <= 1:return []\n",
    "        n = len(array)\n",
    "        tmp = [0]*n\n",
    "    \n",
    "        for i in range(n):\n",
    "            if array[i].isdigit():\n",
    "                tmp[i] = 1\n",
    "            else:\n",
    "                tmp[i] = -1\n",
    "        tmp = list(accumulate(tmp,initial=0))\n",
    "        res = 0\n",
    "        mp = defaultdict(int)\n",
    "        out = []\n",
    "        for i in range(n+1):\n",
    "            if tmp[i] in mp and i-mp[tmp[i]]>res:\n",
    "                res = i-mp[tmp[i]]\n",
    "                out = array[mp[tmp[i]]:i]\n",
    "            elif tmp[i] not in mp:\n",
    "                mp[tmp[i]] = i\n",
    "        print(res)\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        strs = [-1 if s.isdigit() else 1 for s in array]\n",
    "        pre = [0] + strs\n",
    "        for i in range(1, len(strs)+1):\n",
    "            pre[i] = pre[i-1] + strs[i-1]\n",
    "        \n",
    "        begin = dict()\n",
    "        dist, p = 0, 0\n",
    "        for i in range(0, len(strs)+1):\n",
    "            if pre[i] not in begin:\n",
    "                begin[pre[i]] = i\n",
    "            else:\n",
    "                if i - begin[pre[i]] > dist:\n",
    "                    dist = i - begin[pre[i]]\n",
    "                    p = i\n",
    "        return array[p-dist:p] if dist != 0 else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        # 用前缀和处理元素和，「元素和等于 0」等价于「两个前缀和之差等于 0」，进而等价于「两个前缀和相同」\n",
    "        n = len(array)\n",
    "        nums = []\n",
    "        for c in array:\n",
    "            if c.isalpha():\n",
    "                nums.append(1)\n",
    "            else:\n",
    "                nums.append(-1)\n",
    "        dic = dict()\n",
    "        dic[0] = 0 #注意起始位置\n",
    "        pre = [0]*(n+1)\n",
    "        max_cnt = 0\n",
    "        start = 0\n",
    "        # print(nums)\n",
    "        for i in range(1,n+1):\n",
    "            pre[i] = pre[i-1]+nums[i-1] #计算前缀和\n",
    "            if pre[i] in dic:\n",
    "                if i-dic[pre[i]]>max_cnt:\n",
    "                    max_cnt = i- dic[pre[i]]\n",
    "                    start = dic[pre[i]]\n",
    "            else:\n",
    "                dic[pre[i]] = i#记录前缀和与索引的映射关系\n",
    "        return array[start:start+max_cnt]\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        if len(array) <= 1:return []\n",
    "        n = len(array)\n",
    "        tmp = [0]*n\n",
    "    \n",
    "        for i in range(n):\n",
    "            if array[i].isdigit():\n",
    "                tmp[i] = 1\n",
    "            else:\n",
    "                tmp[i] = -1\n",
    "        tmp = list(accumulate(tmp,initial=0))\n",
    "        res = 0\n",
    "        mp = defaultdict(int)\n",
    "        out = []\n",
    "        for i in range(n+1):\n",
    "            if tmp[i] in mp and i-mp[tmp[i]]>res:\n",
    "                res = i-mp[tmp[i]]\n",
    "                out = array[mp[tmp[i]]:i]\n",
    "            elif tmp[i] not in mp:\n",
    "                mp[tmp[i]] = i\n",
    "        #print(res)\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        n = len(array)\n",
    "        cnt = [0]*(n+1)\n",
    "        memo = [-2]*(2*n+1)\n",
    "        memo[n] = -1\n",
    "        left, right = 0, 0\n",
    "        maxl = 0\n",
    "        for i in range(n):\n",
    "            if array[i].isdigit():\n",
    "                cnt[i+1] = cnt[i] + 1\n",
    "            else:\n",
    "                cnt[i+1] = cnt[i] - 1\n",
    "            if memo[cnt[i+1]+n] != -2 and i-memo[cnt[i+1]+n] > maxl:\n",
    "                maxl = i-memo[cnt[i+1]+n]\n",
    "                left = memo[cnt[i+1]+n]+1\n",
    "                right = i+1\n",
    "            elif memo[cnt[i+1]+n] == -2:\n",
    "                memo[cnt[i+1]+n] = i\n",
    "        # for i in range(n, 1, -1):\n",
    "        #     for j in range(n-i+1):\n",
    "        #         if cnt[j] == cnt[j+i]:\n",
    "        #             return array[j:j+i]\n",
    "        return array[left:right]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLongestSubarray(self, array: List[str]) -> List[str]:\n",
    "        strs = [-1 if s.isdigit() else 1 for s in array]\n",
    "        pre = [0] + strs\n",
    "        for i in range(1, len(strs)+1):\n",
    "            pre[i] = pre[i-1] + strs[i-1]\n",
    "        \n",
    "        begin = dict()\n",
    "        dist, p = 0, 0\n",
    "        for i in range(0, len(strs)+1):\n",
    "            if pre[i] not in begin:\n",
    "                begin[pre[i]] = i\n",
    "            else:\n",
    "                if i - begin[pre[i]] > dist:\n",
    "                    dist = i - begin[pre[i]]\n",
    "                    p = i\n",
    "        return array[p-dist:p] if dist != 0 else []\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
